/*              From The Advanced Template Library
                Made From : BaiRX
                Runtime:C++14(-std=c++14)
				Use Dev Tool:Bloodshed Dev-C++ 5.11
				Update:map -> unordered_map 2024/9/1*/
#include<unordered_map>
#include<algorithm>
#define unordered_map std::unordered_map
namespace adv
{
    template <typename T>
    class UnionfindSet
    {
	    unordered_map<T,T> v;
	    int treecount,nodecount;
	    void toinit()
	    {
		    treecount=0;
		    nodecount=0;
		    if(!v.empty())v.clear();
	    }
    public:
	    UnionfindSet()
	    {
		    toinit();
	    }
	    int addtree(T val)
	    {
		    if(have(val))throw "Have the value";
		    v[val]=val;
		    nodecount++;
		    return ++treecount;
	    }
	    bool have(T val)const
	    {
		    if(v.find(val)==v.end())return 0;
		    return 1;
	    }
	    UnionfindSet(T val)
	    {
    		toinit();
	    	addtree(val);
	    }
	    UnionfindSet& operator=(UnionfindSet& u)
	    {
	    	v=u.v;
	    	nodecount=u.nodecount;
	    	treecount=u.treecount;
	    	return *this;
		}
    	int size()const
    	{
    		return nodecount;
	    }
	    int treesize()const
	    {
    		return treecount;
    	}
    	T get(T val)
	    {
	    	if(!have(val))throw "Not Found";
	    	if(val==v[val])return val;
	    	return v[val]=get(v[val]);
	    }
	    void addnode(T val,T father)
	    {
	    	if(have(val))throw "Have the value";
	    	if(!have(father))throw "Not Found Father";
	    	nodecount++;
	    	v[val]=father;
    	}
	    bool judge(T x,T y)
	    {
	    	if(!have(x)||!have(y))throw "Not Found";
	    	return get(x)==get(y);
	    }
	    void merge(T father,T other)
	    {
	    	if(!have(father)||!have(other))throw "Not Found";
	    	T ff=get(father),fo=get(other);
	    	v[fo]=ff;
	    	treecount--;
	    }
	    void del(T val)
	    {
		    if(!have(val))throw "error";
		    if(v[val]==val)treecount--;
		    nodecount--;
		    v.erase(v.find(val));
		    for(auto it=v.begin();it!=v.end();it++)
		    {
			    if(it->second==val)
                {
                    it->second=it->first;
                    treecount++;
                }
		    }
	    }
	    void clear()
	    {
	    	toinit();
	    }
    };
}